{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "db08a393",
   "metadata": {},
   "source": [
    "#### 实验一"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cf9eeb0",
   "metadata": {},
   "source": [
    "##### 任务一：递归求阶乘"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb2a58d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Recursion\n",
    "def function(n):\n",
    "    if n == 1 or n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        result = n * function(n - 1)\n",
    "        print(f\"Result of factorial({n}) = {result}\")\n",
    "        return result\n",
    "\n",
    "#Call recursion    \n",
    "result = function(10)\n",
    "print(f\"The factorial of 10 is {result}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bf6bb1a4",
   "metadata": {},
   "source": [
    "##### 任务二：汉诺塔问题\n",
    " The Tower of Hanoi is a classic problem in recursion.\n",
    " It involves moving a set of disks from one peg to another, using a third peg as a temporary holding area.\n",
    " The goal is to move all disks from the source peg to the target peg, following these rules:\n",
    " 1. Only one disk can be moved at a time.\n",
    " 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty peg.\n",
    " 3. No larger disk may be placed on top of a smaller disk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "635aa69a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def hanoi(n, start, end, temp):\n",
    "    # Base case: if there's only one disk, move it directly from start to end\n",
    "    if n == 1:\n",
    "        print(f\"Move disk 1 from {start} to {end}\")\n",
    "    else:\n",
    "        # Move n-1 disks from start to temp, using end as auxiliary\n",
    "        hanoi(n - 1, start, temp, end)\n",
    "        # Function: move the n disk from start to end\n",
    "        print(f\"Move disk {n} from {start} to {end}\")\n",
    "        # Move n-1 disks from temp to end, using start as auxiliary\n",
    "        hanoi(n - 1, temp, end, start)\n",
    "    \n",
    "#Call recursion\n",
    "arr = 8\n",
    "result = hanoi(arr, 'A', 'B', 'C')\n",
    "def hanoi(n, start, end, temp):\n",
    "    # Base case: if there's only one disk, move it directly from start to end\n",
    "    if n == 1:\n",
    "        print(f\"Move disk 1 from {start} to {end}\")\n",
    "    else:\n",
    "        # Move n-1 disks from start to temp, using end as auxiliary\n",
    "        hanoi(n - 1, start, temp, end)\n",
    "        # Function: move the n disk from start to end\n",
    "        print(f\"Move disk {n} from {start} to {end}\")\n",
    "        # Move n-1 disks from temp to end, using start as auxiliary\n",
    "        hanoi(n - 1, temp, end, start)\n",
    "    \n",
    "#Call recursion\n",
    "arr = 8\n",
    "result = hanoi(arr, 'A', 'B', 'C')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "664e9984",
   "metadata": {},
   "source": [
    "#### 实验二"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6424a6f0",
   "metadata": {},
   "source": [
    "##### 任务一：分治求最大最小值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d12c682b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_max_min(arr, low, high):\n",
    "    if high == low:\n",
    "        return arr[low], arr[low]\n",
    "    else:\n",
    "        mid = (low + high) // 2\n",
    "        max1, min1 = find_max_min(arr, low, mid)\n",
    "        max2, min2 = find_max_min(arr, mid + 1, high)\n",
    "        max_global = max1 if max1 > max2 else max2\n",
    "        min_global = min1 if min1 < min2 else min2\n",
    "        return max_global, min_global\n",
    "\n",
    "arr = [3, 5, 1, 2, 4, 8, 7, 6]\n",
    "max_value, min_value = find_max_min(arr, 0, len(arr) - 1)\n",
    "print(\"最大值：\", max_value)\n",
    "print(\"最小值：\", min_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db98091f",
   "metadata": {},
   "source": [
    "##### 任务二：快速选择第k小元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7842c998",
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(arr, low, high):\n",
    "    pivot = arr[high]\n",
    "    i = low - 1\n",
    "    for j in range(low, high):\n",
    "        if arr[j] < pivot:\n",
    "            i += 1\n",
    "            arr[i], arr[j] = arr[j], arr[i]\n",
    "    arr[i + 1], arr[high] = arr[high], arr[i + 1]\n",
    "    return i + 1\n",
    "\n",
    "def quick_select(arr, k):\n",
    "    if len(arr) == 1:\n",
    "        return arr[0]\n",
    "    pivot_index = partition(arr, 0, len(arr) - 1)\n",
    "    if k - 1 == pivot_index:\n",
    "        return arr[pivot_index]\n",
    "    elif k - 1 < pivot_index:\n",
    "        return quick_select(arr[:pivot_index], k)\n",
    "    else:\n",
    "        return quick_select(arr[pivot_index + 1:], k - pivot_index - 1)\n",
    "\n",
    "arr = [3, 5, 1, 2, 4, 8, 7, 6]\n",
    "k = 3\n",
    "result = quick_select(arr, k)\n",
    "print(f\"第{k}小的元素是: {result}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c77a18f",
   "metadata": {},
   "source": [
    "#### 实验三"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56bb8ed1",
   "metadata": {},
   "source": [
    "##### 任务一：活动选择问题（贪心）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4414d8f2",
   "metadata": {},
   "outputs": [],
   "source": [
    "joblist = [['a', 8, 10], ['b', 1, 5], ['c', 4, 8], \n",
    "           ['d', 1, 3], ['e', 6, 9], ['f', 2, 4], \n",
    "           ['g', 4, 7], ['h', 1, 5], ['i', 6, 12]]\n",
    "joblist.sort(key = lambda x: x[2])\n",
    "Last_end = 0\n",
    "selected = []\n",
    "for name, start, end in joblist:\n",
    "    if start >= Last_end:\n",
    "        selected.append(name)\n",
    "        Last_end = end\n",
    "print(\"选择的活动：\", selected)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "818e5959",
   "metadata": {},
   "source": [
    "##### 任务二：Dijkstra 单源最短路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a5d71dc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(graph, start):\n",
    "    distances = {node: float('inf') for node in graph}\n",
    "    distances[start] = 0\n",
    "    previous_nodes = {node: None for node in graph}\n",
    "    unvisited_nodes = set(graph.keys())\n",
    "    while unvisited_nodes:\n",
    "        current_node = min(unvisited_nodes, key=lambda node: distances[node])\n",
    "        if distances[current_node] == float('inf'):\n",
    "            break\n",
    "        for neighbor, weight in graph[current_node].items():\n",
    "            if neighbor in unvisited_nodes:\n",
    "                new_distance = distances[current_node] + weight\n",
    "                if new_distance < distances[neighbor]:\n",
    "                    distances[neighbor] = new_distance\n",
    "                    previous_nodes[neighbor] = current_node\n",
    "        unvisited_nodes.remove(current_node)\n",
    "    return distances, previous_nodes\n",
    "\n",
    "graph = {'s': {'a': 4, 'c': 11, 'b':6},\n",
    "         'a': {'b': 3},\n",
    "         'c': {'d': 2},\n",
    "         'b': {'c': 5, 'e': 4},\n",
    "         'e': {'c': 7, 'd': 3},\n",
    "         'd': {}}\n",
    "print(\"请输入起点节点：\")\n",
    "start_node = input()\n",
    "print(\"请输入终点节点：\")\n",
    "node = input()\n",
    "distances, previous_nodes = dijkstra(graph, start_node)\n",
    "if node not in graph:\n",
    "    print(f\"节点 {node} 不在图中\")\n",
    "else:\n",
    "    print(f\"{start_node}到节点 {node} 的最短距离是 {distances[node]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0abee2c6",
   "metadata": {},
   "source": [
    "#### 实验四"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a66da23b",
   "metadata": {},
   "source": [
    "\n",
    "##### 题目一：编程实现10张扑克牌配对问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "099bc344",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "import random\n",
    "\n",
    "def generate_cards(n):\n",
    "    SUITS = 'cdhs'\n",
    "    RANKS = '23456789TJQKA'\n",
    "    DECK = tuple(''.join(card) for card in itertools.product(RANKS, SUITS))\n",
    "    hand = random.sample(DECK, n)\n",
    "    return hand\n",
    "\n",
    "def rank_value(card):\n",
    "    RANKS = '23456789TJQKA'\n",
    "    return RANKS.index(card[0]) + 2\n",
    "\n",
    "def max_pairs_dp_with_path(cards, target=13):\n",
    "    n = len(cards)\n",
    "    values = [rank_value(c) for c in cards]\n",
    "    size = 1 << n\n",
    "    dp = [0] * size\n",
    "    path = [None] * size  # 记录转移路径\n",
    "\n",
    "    for mask in range(size):\n",
    "        # 找到未配对的第一个牌i\n",
    "        idxs = [i for i in range(n) if not (mask & (1 << i))]\n",
    "        if len(idxs) < 2:\n",
    "            continue\n",
    "        i = idxs[0]\n",
    "        for j in idxs[1:]:\n",
    "            if values[i] + values[j] == target:\n",
    "                next_mask = mask | (1 << i) | (1 << j)\n",
    "                if dp[next_mask] < dp[mask] + 1:\n",
    "                    dp[next_mask] = dp[mask] + 1\n",
    "                    path[next_mask] = (mask, i, j)\n",
    "    # 回溯找到配对方案\n",
    "    res_pairs = []\n",
    "    cur = size - 1\n",
    "    while path[cur]:\n",
    "        prev, i, j = path[cur]\n",
    "        res_pairs.append((cards[i], cards[j]))\n",
    "        cur = prev\n",
    "    res_pairs.reverse()\n",
    "    return dp[size-1], res_pairs\n",
    "\n",
    "def main():\n",
    "    hand = generate_cards(10)\n",
    "    print(\"10张牌:\", ' '.join(hand))\n",
    "    max_pairs, pairs = max_pairs_dp_with_path(hand)\n",
    "    print(f\"最多可以配对 {max_pairs} 对。\")\n",
    "    if pairs:\n",
    "        print(\"配对方案：\")\n",
    "        for a, b in pairs:\n",
    "            print(f\"{a} - {b}\")\n",
    "    if max_pairs * 2 == 10:\n",
    "        print(\"全部牌可以完美配对！\")\n",
    "    else:\n",
    "        print(f\"有 {10 - max_pairs*2} 张牌无法配对。\")\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4aff7a41",
   "metadata": {},
   "source": [
    "##### 题目二：编程实现108张扑克牌的21点问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "60f87805",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 随机产生n张扑克\n",
    "def generate_cards(num):\n",
    "    import random\n",
    "    hand = [random.randint(1, 11) for i in range(num)]\n",
    "    random.shuffle(hand)\n",
    "    random.shuffle(hand)\n",
    "    return hand\n",
    "\n",
    "def max_blackjack_score(cards, max_point=21):\n",
    "    n = len(cards)\n",
    "    # dp[i]：点数i是否可达\n",
    "    dp = [False] * (max_point + 1)\n",
    "    dp[0] = True\n",
    "    for card in cards:\n",
    "        # 逆序遍历，避免重复选同一张牌\n",
    "        for i in range(max_point, card - 1, -1):\n",
    "            if dp[i - card]:\n",
    "                dp[i] = True\n",
    "        # 如果是A(1)还能当11用\n",
    "        if card == 1:\n",
    "            for i in range(max_point, 11 - 1, -1):\n",
    "                if dp[i - 11]:\n",
    "                    dp[i] = True\n",
    "    # 找到不超过21的最大可达点数\n",
    "    for score in range(max_point, -1, -1):\n",
    "        if dp[score]:\n",
    "            return score\n",
    "    return 0\n",
    "\n",
    "def main():\n",
    "    cards = generate_cards(108)\n",
    "    print(\"108张牌：\", cards)\n",
    "    best = max_blackjack_score(cards)\n",
    "    print(\"108张牌可达到的最大不爆点数为：\", best)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5cc1b505",
   "metadata": {},
   "source": [
    "#### 实验五"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "27a0e95b",
   "metadata": {},
   "source": [
    "##### 题目一：用深度优先遍历算法找最大的岛屿"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7ae9cc29",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 如图所示，为了方便计算，我们使用一个二维数组来表示一片海域，\n",
    "# 用0表示水面，用1表示陆地，我们的任务是找出其中最大的岛屿。\n",
    "# 注意，岛屿是指上下左右四个方向相连接的陆地区域。\n",
    "def max_island_area(grid):\n",
    "    if not grid or not grid[0]:\n",
    "        return 0\n",
    "\n",
    "    m, n = len(grid), len(grid[0])\n",
    "    visited = [[False]*n for _ in range(m)]\n",
    "\n",
    "    def dfs(x, y):\n",
    "        if x < 0 or x >= m or y < 0 or y >= n:\n",
    "            return 0\n",
    "        if grid[x][y] == 0 or visited[x][y]:\n",
    "            return 0\n",
    "        visited[x][y] = True\n",
    "        area = 1\n",
    "        # 四个方向\n",
    "        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "            area += dfs(x+dx, y+dy)\n",
    "        return area\n",
    "\n",
    "    max_area = 0\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if grid[i][j] == 1 and not visited[i][j]:\n",
    "                area = dfs(i, j)\n",
    "                max_area = max(max_area, area)\n",
    "    return max_area\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    grid = [\n",
    "        [0,0,0,0,0,1,1,0],\n",
    "        [0,1,1,0,0,1,1,0],\n",
    "        [0,1,1,0,0,0,0,0],\n",
    "        [0,0,1,0,0,0,1,1],\n",
    "        [0,0,0,0,0,0,0,0],\n",
    "        [0,0,1,1,0,0,0,0],\n",
    "        [0,0,0,1,0,0,0,1],\n",
    "    ]\n",
    "    print(\"最大岛屿面积为:\", max_island_area(grid))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b209248",
   "metadata": {},
   "source": [
    "##### 题目二：0-1背包问题，动态规划求最大价值\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab54c205",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def knapsack(weights, values, capacity):\n",
    "    n = len(weights)\n",
    "    # dp[i][j]: 前i件物品，容量为j时的最大价值\n",
    "    dp = [[0] * (capacity + 1) for _ in range(n + 1)]\n",
    "\n",
    "    for i in range(1, n + 1):\n",
    "        for w in range(capacity + 1):\n",
    "            if weights[i - 1] > w:\n",
    "                dp[i][w] = dp[i - 1][w]\n",
    "            else:\n",
    "                dp[i][w] = max(\n",
    "                    dp[i - 1][w],  # 不选第i件\n",
    "                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  # 选第i件\n",
    "                )\n",
    "    return dp[n][capacity]\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    weights = [2, 4, 5, 3]   # 足球、早冰鞋、随身听、单词书\n",
    "    values = [5, 4, 6, 2]\n",
    "    capacity = 9\n",
    "    max_value = knapsack(weights, values, capacity)\n",
    "    print(f\"背包最大可带物品总价值为: {max_value}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b89a8e30",
   "metadata": {},
   "source": [
    "##### 题目三：金矿问题（0-1背包变形）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "77b8fa1b",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def max_gold(gold, people, total_people):\n",
    "    n = len(gold)\n",
    "    # dp[i][j]: 前i个金矿，j个人时的最大黄金\n",
    "    dp = [[0] * (total_people + 1) for _ in range(n + 1)]\n",
    "    for i in range(1, n + 1):\n",
    "        for j in range(total_people + 1):\n",
    "            if people[i - 1] > j:\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "            else:\n",
    "                dp[i][j] = max(\n",
    "                    dp[i - 1][j],  # 不挖第i座金矿\n",
    "                    dp[i - 1][j - people[i - 1]] + gold[i - 1]  # 挖第i座金矿\n",
    "                )\n",
    "    # 追溯选了哪些金矿\n",
    "    j = total_people\n",
    "    chosen = []\n",
    "    for i in range(n, 0, -1):\n",
    "        if dp[i][j] != dp[i-1][j]:\n",
    "            chosen.append(i)  # 题目编号从1开始\n",
    "            j -= people[i-1]\n",
    "    chosen.reverse()\n",
    "    return dp[n][total_people], chosen\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # 金矿储量\n",
    "    gold = [500, 300, 150, 200, 350, 350]\n",
    "    # 所需工人数\n",
    "    people = [6, 5, 3, 4, 3, 3]\n",
    "    total_people = 16\n",
    "    max_gold_num, mines = max_gold(gold, people, total_people)\n",
    "    print(\"最多可采黄金量:\", max_gold_num)\n",
    "    print(\"应选择挖掘的矿场编号:\", mines)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bdc7039d",
   "metadata": {},
   "source": [
    "#### 实验六"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "29fc093f",
   "metadata": {},
   "source": [
    "##### 题目一：活动选择问题（贪心算法实现）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47836bb8",
   "metadata": {},
   "outputs": [],
   "source": [
    "#设计Python程序利用贪心算法，从一组活动中选出最大数量的互不冲突的活动（活动时间不能重叠）。\n",
    "\n",
    "#输入参数：活动开始时间 start = [1, 3, 0, 5, 8, 5]，活动结束时间 end = [2, 4, 6, 7, 9, 9]，活动数量 n = 6。\n",
    "\n",
    "#要求：\n",
    "#输出选择的活动数量及具体活动； \n",
    "#分析算法的时间复杂度。\n",
    "\n",
    "# 输入参数\n",
    "start = [1, 3, 0, 5, 8, 5]\n",
    "end =   [2, 4, 6, 7, 9, 9]\n",
    "n = 6\n",
    "\n",
    "# 将活动编号、开始时间、结束时间打包成元组列表\n",
    "activities = list(zip(range(n), start, end))  # (编号, 开始, 结束)\n",
    "activities.sort(key = lambda x: x[2])\n",
    "Last_end = 0\n",
    "selected = []\n",
    "for name, start, end in activities:\n",
    "    if start >= Last_end:\n",
    "        selected.append(name)\n",
    "        Last_end = end\n",
    "print(\"选择的活动：\", selected)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8e8da6f",
   "metadata": {},
   "source": [
    "时间复杂度分析：\n",
    "\n",
    "- 排序：O(n log n)，按结束时间升序排列\n",
    "- 遍历选择：O(n)，依次选择活动时间\n",
    "- 总体：O(n log n)，近似取最大值\n",
    "\n",
    "总结： 该流程保证每次都选择最早结束且不冲突的活动，从而得到最多的互不冲突活动集合。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7851e48b",
   "metadata": {},
   "source": [
    "##### 题目二：0-1背包问题，动态规划求解"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dd1538fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "#题目二：设计Python程序，解决0-1背包问题：给定背包容量和一组物品的重量与价值，\n",
    "# 选择装入背包的物品，使得总价值最大且不超容量。\n",
    "# 输入参数：\n",
    "# 物品重量 wt = [2, 3, 4, 5]，\n",
    "# 物品价值 val = [3, 4, 5, 6]，\n",
    "# 背包容量 W = 8，\n",
    "# 物品数量 n = 4。\n",
    "\n",
    "# 要求：\n",
    "# 1）输出背包能装入的最大价值；\n",
    "# 2）输出具体装入的物品编号。\n",
    "\n",
    "wt = [2, 3, 4, 5]\n",
    "val = [3, 4, 5, 6]\n",
    "W = 8\n",
    "n = 4\n",
    "\n",
    "#dp[i][j]表示前i个物品在容量为j的背包中能装入的最大价值\n",
    "dp = [[0] * (W + 1) for _ in range(n + 1)]\n",
    "\n",
    "for i in range(1, n + 1):\n",
    "    for w in range(W + 1):\n",
    "        if wt[i - 1] > w:\n",
    "            dp[i][w] = dp[i - 1][w]\n",
    "        else:\n",
    "            dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i - 1]] + val[i - 1])\n",
    "\n",
    "print(\"背包能装入的最大价值：\", dp[n][W])\n",
    "\n",
    "# 回溯找出具体装入的物品编号\n",
    "res = []\n",
    "w = W\n",
    "for i in range(n, 0, -1):\n",
    "    if dp[i][w] != dp[i - 1][w]:\n",
    "        res.append(i - 1)  # 物品编号（从0开始）\n",
    "        w -= wt[i - 1]\n",
    "res.reverse()\n",
    "print(\"装入背包的物品编号：\", res)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "616d9843",
   "metadata": {},
   "source": [
    "##### 题目三：计算矩阵链乘法的最小计算代价。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8bd1822e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定输入参数：\n",
    "# 矩阵链维度数组 p = [30, 35, 15, 5, 10, 20, 25]\n",
    "# （表示6个矩阵的维度分别为30×35、35×15、...、20×25）。\n",
    "# 要求：\n",
    "# 1）输出最小标量乘法次数；\n",
    "# 2）输出最优括号化方案\n",
    "\n",
    "def matrix_chain_order(p):\n",
    "    n = len(p) - 1  # 矩阵个数\n",
    "    m = [[0] * n for _ in range(n)]  # 最小乘法次数表\n",
    "    s = [[0] * n for _ in range(n)]  # 最优断开点表\n",
    "\n",
    "    for l in range(2, n + 1):  # l为链长度\n",
    "        for i in range(n - l + 1):\n",
    "            j = i + l - 1\n",
    "            m[i][j] = float('inf')\n",
    "            for k in range(i, j):\n",
    "                q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1]\n",
    "                if q < m[i][j]:\n",
    "                    m[i][j] = q\n",
    "                    s[i][j] = k\n",
    "    return m, s\n",
    "\n",
    "def print_optimal_parens(s, i, j):\n",
    "    if i == j:\n",
    "        return f\"A{i+1}\"\n",
    "    else:\n",
    "        return \"(\" + print_optimal_parens(s, i, s[i][j]) + \" x \" + print_optimal_parens(s, s[i][j] + 1, j) + \")\"\n",
    "\n",
    "# 输入参数\n",
    "p = [30, 35, 15, 5, 10, 20, 25]\n",
    "\n",
    "# 计算\n",
    "m, s = matrix_chain_order(p)\n",
    "min_cost = m[0][len(p)-2]\n",
    "optimal_parens = print_optimal_parens(s, 0, len(p)-2)\n",
    "\n",
    "print(\"最小标量乘法次数：\", min_cost)\n",
    "print(\"最优括号化方案：\", optimal_parens)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
